We provide an algorithm for properly learning mixtures of twosingle-dimensional Gaussians without any separability assumptions. Given$\tilde{O}(1/\varepsilon^2)$ samples from an unknown mixture, our algorithmoutputs a mixture that is $\varepsilon$-close in total variation distance, intime $\tilde{O}(1/\varepsilon^5)$. Our sample complexity is optimal up tologarithmic factors, and significantly improves upon both Kalai et al., whosealgorithm has a prohibitive dependence on $1/\varepsilon$, and Feldman et al.,whose algorithm requires bounds on the mixture parameters and dependspseudo-polynomially in these parameters. One of our main contributions is an improved and generalized algorithm forselecting a good candidate distribution from among competing hypotheses.Namely, given a collection of $N$ hypotheses containing at least one candidatethat is $\varepsilon$-close to an unknown distribution, our algorithm outputs acandidate which is $O(\varepsilon)$-close to the distribution. The algorithmrequires ${O}(\log{N}/\varepsilon^2)$ samples from the unknown distribution and${O}(N \log N/\varepsilon^2)$ time, which improves previous such results (suchas the Scheff\'e estimator) from a quadratic dependence of the running time on$N$ to quasilinear. Given the wide use of such results for the purpose ofhypothesis selection, our improved algorithm implies immediate improvements toany such use.
展开▼
